package frist50;

import org.junit.jupiter.api.Test;

import java.util.*;

public class T0030 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list = new ArrayList<>();
//        int[] arr = new int[words.length];
//        Arrays.fill(arr, -1);
        Map<String, Integer> hashmap = new HashMap<>();
        for (String str : words) {
            if (hashmap.containsKey(str)) {
                int sum = hashmap.get(str);
                hashmap.remove(str);
                hashmap.put(str, sum + 1);
            }else {
                hashmap.put(str,  1);
            }
        }
        int len = words[0].length();
        for (int i = 0; i < len; i++) {
            int left = i;
            int sum = 0;
            for (int j = i; j + len - 1 < s.length(); j += len) {
                String str = s.substring(j, j + len);
                if (!hashmap.containsKey(str)) {
                    hashmap.clear();
                    for (String word : words) {
                        if (hashmap.containsKey(word)) {
                            int wordSum = hashmap.get(word);
                            hashmap.remove(word);
                            hashmap.put(word, wordSum + 1);
                        }else {
                            hashmap.put(word,  1);
                        }
                    }
                    left = j + len;
                    sum = 0;
                } else {
                    int v = hashmap.get(str);
                    if (v > 0) {
                        hashmap.put(str, v - 1);
                        sum++;
                        if (sum == words.length) {
                            list.add(left);
                            int p = hashmap.get(s.substring(left, left + len));
                            hashmap.put(s.substring(left, left + len), p + 1);
                            left += len;
                            sum--;
                        }
                    } else {
                        int k;
                        for (k = left; k < j; k += len) {
                            String ks = s.substring(left, left + len);
                            if (ks.equals(str)) {
                                left += len;
                                sum--;
                                break;
                            }
                            int p = hashmap.get(ks);
                            hashmap.put(ks, p + 1);
                            left += len;
                            sum--;
                        }
                        sum++;
                    }
                }
            }
            hashmap.clear();
            for (String word : words) {
                if (hashmap.containsKey(word)) {
                    int wordSum = hashmap.get(word);
                    hashmap.remove(word);
                    hashmap.put(word, wordSum + 1);
                }else {
                    hashmap.put(word,  1);
                }
            }
        }
        return list;
    }

//    public int find(String str, String[] words) {
//        for (int i = 0; i < words.length; i++) {
//            if (words[i].equals(str)) {
//                return i;
//            }
//        }
//        return -1;
//    }


    @Test
    public void test() {
        String s = "aaaaaaa";
        String[] words = {"aa", "aa"};
        System.out.println(findSubstring(s, words).toString());
    }
}
